package 算法.练习1;

import 算法.NiuKe.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

import static 算法.NiuKe.JZ.JZ4.reConstructBinaryTree;

/**
 * @author:谢君臣
 * @Date:2021/7/20-16:40
 * @version:1.0
 * @function:
 */
public class NC102 {
    public static void main(String[] args) {
        int [] pre = {1,2,4,5,6,7,3};
        int [] in = {4,2,6,5,7,1,3};
        算法.NiuKe.TreeNode treeNode = reConstructBinaryTree(pre, in);
        lowestCommonAncestor1(treeNode,4,6);
        System.out.println(Arrays.toString(IN(treeNode, 0).toArray()));
    }

    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here

        List<Integer> list1 = PRE(root,o1);
        List<Integer> list2 = PRE(root,o2);
        return 0;
    }

    private static List<Integer> IN(TreeNode root, int o1) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root!=null||!stack.isEmpty()){
            while (root!=null){
                stack.add(root);
                root = root.left;
            }
            if (!stack.isEmpty()){
                TreeNode node = stack.pop();
                if (node.right!=null) root = node.right;
                else root = null;
                res.add(node.val);
            }

        }
        return res;
    }
    private static List<Integer> PRE(TreeNode root, int o1) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            if (pop.val==o1){
                return res;
            }else {
                res.add(pop.val);
                if (pop.right!=null) stack.add(root.right);
                if (pop.left!=null) stack.add(root.left);
            }
        }
        return res;
    }

    public static int lowestCommonAncestor1 (TreeNode root, int o1, int o2) {
        // write code
        if (root==null) return -1;
        if (root.val==o1||root.val==o2) return root.val;
        int l = lowestCommonAncestor1(root.left,o1,o2);
        int r = lowestCommonAncestor1(root.right,o1,o2);
        if (l==-1)return r;
        if (r==-1)return l;
        return root.val;
    }
}
